1. Field of the present invention
The present invention relates to a delay guarantee path setting system for traffic transfer.
2. Description of the Related Art
Upon traffic transfer in a network, in order to guarantee Qos (quality of service) concerning a bandwidth or delay, it is necessary to search for such a route that meets a Qos request and set the obtained route as a path by referring configuration information or resources information of the network.
More specifically, a router in the network or network management control device has a database storing the configuration information or resources information of the network and searches the database for such a path that meets the QoS request in a given segment requested by a user. The path selected from among this search undergoes paths setting with an explicit route using a signaling protocol, for example, RSVP-TE (Resource reSerVation Protocol Traffic Engineering extension) for an MPLS (Multi-Protocol Label Switching) network. Traffic is then transferred to the path.
As a conventional art for searching for a path that complies with requested bandwidth and delay, there is a method in which a link having an available bandwidth smaller than the requested bandwidth is pruned from the network, and then a shortest path (minimum delay path) is detected where a target delay is set as a metric by using an existing SPF (Shortest Path First) algorithm such as Dijkstra's algorithm (see Non-patent document 1, for example).
In addition, another algorithm is exemplified, which defines a cost value for each link and detects a path that complies with a limitation on a delay and requires the lowest cost with a view to enhancing usability of network resources (bandwidth) as compared with the aforementioned method (see Non-patent document 2, etc.). This cost value denotes infrequency of selection of the link concerned. In general, a constant value is employed (the same value in all the links).
<Minimum Delay Path Selecting Method>
As a conventional art, there is a system where a link having an available bandwidth smaller than the requested bandwidth is checked off from a list of path setting targets in the network, and then a shortest path (minimum delay path) is detected, in which a target delay is set as a metric using an existing SPF algorithm (hereinafter, referred to as minimum delay path selecting method).
Referring to FIGS. 8, 9, 10, and 11, the minimum delay path selecting method as one of the conventional arts will be described below.
Prior to an explanation about the minimum delay path selecting method, given as an example is a network configuration of FIG. 8, where five transfer devices (nodes 1 to 5 in the figure) are connected to each other via communication media 12, 13, 23, 24, 35, and 45.
Links connecting between the respective nodes that constitute the network of FIG. 8 have specific delay times and available bandwidths, respectively. A link 12 connecting between the node 1 and the node 2, a link 13 connecting between the node 1 and the node 3, and a link 45 connecting between the node 4 and the node 5 each have a delay time of 10 ms (value (1) of FIG. 8) and an available bandwidth of 100 Mbps (value (2) of FIG. 8). A link 23 connecting between the node 2 and the node 3 and a link 24 connecting between the node 2 and the node 4 each have a delay time of 100 ms and an available bandwidth of 100 Mbps. A link 35 connecting between the node 3 and the node 5 has a delay time of 10 ms and an available bandwidth of 10 Mbps.
A delay time of the links is kept constant all the time. However, with regard to the available bandwidth, in response to each request, a bandwidth of a link on a requested path is used, and thus the available bandwidth is narrowed by the used amount. Note that for ease of explanation, the explanation is centered on one-way communication of the link as indicated by the arrow in the figure.
Referring now to FIGS. 10 and 11, description is given of an operation of a conventional system (hereinafter, referred to as a conventional system 1) in the network configuration shown in FIG. 8, which employs the minimum delay path selecting method as the conventional art. Note that the description is given with reference to an operation flow of a flowchart of FIG. 9 taking as an example a case of receiving a delay guarantee path setting request (request 1) aiming at a path having a bandwidth of 5 Mbps and a delay time of 200 ms or shorter, and a case of receiving, after the request 1 is received, a delay guarantee path setting request (request 2) aiming at a path having a bandwidth of 10 Mbps and a delay time of 50 ms or shorter.
FIG. 9 is a flowchart illustrative of a minimum delay path selecting method. FIG. 10 shows an operation example of the conventional system 1 in the case of receiving the delay guarantee path setting request (request 1) aiming at a path having a bandwidth of 5 Mbps and a delay time of 200 ms for connecting the node 1 and the node 5.
When receiving the request 1 (S901 of FIG. 9), the conventional system 1 detects any path having a requested bandwidth in a requested segment (in this example, the requested segment is assumed to start with the node 1 and end with the node 5). More specifically, the conventional system 1 selects a link having an available bandwidth (value (2) of FIG. 10) larger than a requested bandwidth, 5 Mbps, from among the links for connecting between the node 1 and the node 5. In other words, at this point, the system excludes links not having an available bandwidth corresponding to the requested bandwidth (5 Mbps) (S902 of FIG. 9). In the case of FIG. 10, there is no link short of the bandwidth.
With this operation, the conventional system 1 detects the following three paths.                Path 1: Node 1->Node 3->Node 5        Path 2: Node 1->Node 2->Node 3->Node 5        Path 3: Node 1->Node 2->Node 4->Node 5        
Next, the conventional system 1 calculates the total delay time for each detected path, and selects a path having the minimum total delay time (S903 of FIG. 9).
Regarding the total delay time for each path, the total delay time is, in a path 1, 20 ms of which the link 13 accounts for 10 ms and the link 35 accounts for 10 ms. The total delay time is, in a path 2, 120 ms of which the link 12 accounts for 10 ms, the link 23 accounts for 100 ms, and the link 35 accounts for 10 ms. Similarly, the total delay time is, in a path 3, 120 ms. Thus, the path 1 whose total delay time is minimum is selected.
Then, the total delay time (path 1: 20 ms) in the path selected this time matches with the requested delay time (200 ms or shorter) (S904 of FIG. 9; YES), so the request is judged as acceptable (S905 of FIG. 9). As a result, the requested bandwidth, 5 Mbps, is reserved in the link 13 and link 35 on the path 1. Hence, the available bandwidth is reduced.
In addition, referring to FIG. 11, description is given below of an operation of the conventional system 1 in receiving a delay guarantee path setting request (request 2) aiming at a path having a bandwidth of 10 Mbps and a delay time of 50 ms or shorter for connecting the node 1 and the node 5. FIG. 11 shows an operation example of the conventional system 1 in receiving the request 2 in a state where the target bandwidth is reserved on the path 1 in the mode shown in FIG. 10. Therefore, the available bandwidths of the link 13 and the link 35 of FIG. 11 are narrowed by the requested bandwidth of the request 1 and thus decreased down to 95 Mbps and 5 Mbps, respectively.
Upon receiving the request 2 in the aforementioned state (S901 of FIG. 9), the conventional system 1 detects a path having the requested bandwidth among the requested paths as in the case of receiving the request 1. More specifically, the conventional system 1 selects a link, among links connecting between the node 1 and the node 5, which has an available bandwidth larger than the requested bandwidth, 10 Mbps (value (2) of FIG. 11). In other words, at this point, the conventional system 1 excludes a link not having an available bandwidth equivalent to the requested bandwidth (10 Mbps). In short, the link 35 has only an available bandwidth of 5 Mbps and therefore is pruned upon selecting a path (S902 of FIG. 9).
Accordingly, the path detected by the conventional system 1 is the path 3 alone.                Path 3: Node 1->Node 2->Node 4->Node 5        
The total delay time of the path 3 counts up to 120 ms (S903 of FIG. 9). However, the total delay time of the path 3 is longer than the requested delay time of 50 ms (S904 of FIG. 9; NO), and does not comply with the requested delay. Hence, this request is judged unacceptable (S906 of FIG. 9).
<Delay Limitation Minimum Hop Path Selecting Method>
As another conventional art, there is an algorithm for defining a cost value for each link and detecting a path that complies with limitations on a delay and has a minimum cost value. With this conventional art, a constant cost value is employed (the same value for all the links). This conventional art provides a method (hereinafter, referred to as delay limitation minimum hop path selecting method) of selecting a path that complies with the limitations on the bandwidth and delay and has the minimum number of hops by setting the constant cost value.
Here, referring to FIGS. 13 and 14, this delay limitation minimum hop path selecting method employed in the conventional art is described below based on an operation flow of a flowchart of FIG. 12. FIG. 12 is a flowchart illustrative of the delay limitation minimum hop path selecting method. Prior to an explanation thereof, for ease of comparison, the same network configuration and case (in receiving the request 1 and request 2) as the aforementioned conventional system 1 are employed.
FIGS. 13 and 14 each show an operation example of a conventional system employing the delay limitation minimum hop path selecting method used in the conventional art (hereinafter, referred to as a conventional system 2). As shown in FIGS. 13 and 14, the delay time (value (1) of the figures) and available bandwidth (value (2) of the figures) of the respective links are the same as those in the conventional system 1; however, the conventional system 2 differs from the conventional system 1 in that cost values (values (3) of the figures) are additionally set.
FIG. 13 shows an operation example of the conventional system 2 upon receiving the request 1 (delay guarantee path setting request aiming at a path having a bandwidth 5 Mbps and delay time 200 ms) for connecting the node 1 and the node 5.
The conventional system 2 detects, in response to the request 1 (S911 of FIG. 12) a path that has a requested bandwidth within a requested segment (segment started with the node 1 and the ended with the node 5) (S912 of FIG. 12). This operation is similar to the conventional system 1.
The conventional system 2 detects the following three paths.                Path 1: Node 1->Node 3->Node 5        Path 2: Node 1->Node 2->Node 3->Node 5        Path 3: Node 1->Node 2->Node 4->Node 5        
Next, the conventional system 2 calculates the total delay time for each detected path, and detects among the paths, a path having a delay time equal to or shorter than a requested delay time of 200 ms.
Regarding the total delay time for each path, the total delay time is 20 ms in the path 1, 120 ms in the path 2, and 120 ms in the path 3. Therefore, all the paths comply with the requested delay time (200 ms) or shorter (S913 of FIG. 12; YES).
Subsequently, the conventional system 2 calculates a sum of cost values of the links on the respective paths (total cost value) (S915 of FIG. 12). In short, in the path 1, the cost value of the link 13 is 1 and the cost value of the link 35 is 1, so the total cost value equals 2. Similarly, the total cost value of the path 2 equals 3 and the total cost value of the path 3 equals 3, respectively.
Then, the conventional system 2 selects a path having the minimum total cost value, out of the paths that comply with a requested delay time, that is, the path 1 (S916 of FIG. 12), and allows acceptance of the request 1 (S917 of FIG. 12). As a result, the link 13 and link 35 on the path 1 are occupied by the requested bandwidth of 5 Mbps, and thus decrease their available bandwidths.
In addition, referring to FIG. 14, description is given below of an operation of the conventional system 2 in receiving, afterward, the request 2 (delay guarantee path setting request aiming at a path having a bandwidth 10 Mbps and delay time 50 ms or shorter) for connecting the node 1 and the node 5. FIG. 14 shows an operation example of the conventional system 2 upon receiving the request 2 in a state where the requested bandwidth is reserved on the path 1 in the mode shown in FIG. 13. Therefore, the available bandwidths of the link 13 and link 35 are reduced by the requested bandwidth of the request 1, and reach 95 Mbps and 5 Mbps, respectively.
The conventional system 2 detects, in receiving the request 2 (S911 of FIG. 12) under the aforementioned state, a path that complies with the requested bandwidth, out of the requested paths as in the case of receiving the request 1 (S912 of FIG. 12).
Thus, the path detected by the conventional system 2 is the path 3 alone.                Path 3: Node 1->Node 2->Node 4->Node 5        
Here, the total delay time of the path 3 equals 120 ms. However, the total delay time of the path 3 is longer than the requested delay time, 50 ms (S913 of FIG. 12; NO), and thus does not comply with the requested delay time, so the request is judged unacceptable (S914 of FIG. 12).
Note that the conventional art documents concerning the present invention are as follows. The conventional art documents are “Japanese Patent Application Laid-Open Publication No. 07-245626”, “Japanese Patent Application Laid-Open Publication No. 2003-502941”, “Zheng Wang and Jon Crowcroft, “Quality of Service Routing for Supporting Multimedia Applications”, IEEE Journal on Selected Areas in Communications, Vol. 14, no. 7, pp. 1228-1234, September 1996”, and “Turgay Korkmaz, Marwan Krunz, and Spyros Tragoudas, “An efficient algorithm for finding a path subject to two additive constraints”, Computer Communications Journal, Vol. 25, No. 3, pp. 225-238, February 2002”.
However, in the minimum delay path selecting method (conventional system 1) of the conventional art, the minimum delay path is always selected. Hence, a link with a smaller delay is more likely to be selected and thus its bandwidth is concentratedly used. If some link leaves no available bandwidth, which narrows the list of candidate paths to be selected, resulting in a low possibility that the request is accepted.
The minimum delay path is also selected with respect to a request that imposes not so strict limitations on a delay. As a result, the bandwidth of the minimum delay path is used, resulting in a low possibility that any request that imposes more strict limitations on the delay is accepted thereafter.
In the delay limitation minimum hop path selecting method of another conventional art (conventional system 2), if a request aiming at the same required bandwidth is accepted, a path having the smaller number of links is selected. Thus, there is an advantage that the use amount of bandwidth throughout the network can be minimized. However, an available bandwidth in each link is out of consideration, so a link insufficient in free bandwidth may be selected, leading to nonuniform use amounts of bandwidth. As a result, a call loss (in case that the request is not accepted because of failing in detection of a path that meets requests) increases.
In this way, in searching and setting a path that guarantees bandwidth and delay, the conventional art for selecting the minimum delay path or delay limitation minimum hop path is inefficient in usability of network resources, and suffers from a problem in that a larger number of delay guarantee path setting requests cannot be accepted.